InforLorV4, Main, Exploration, bibRecord, 006380

An NP decision procedure for protocol insecurity with XOR

Identifieur interne : 006380 ( Main/Exploration ); précédent : 006379; suivant : 006381

An NP decision procedure for protocol insecurity with XOR

Auteurs : Yannick Chevalier [France] ; Ralf Küsters [Allemagne] ; Michaël Rusinowitch [France] ; Mathieu Turuani [France]

Source :

Theoretical computer science [ 0304-3975 ] ; 2005.

RBID : Pascal:05-0253621

Descripteurs français

Pascal (Inist)
- Décision, Oracle, Déduction, Vérification, Complexité, Informatique théorique, Protocole cryptographique, Protocole sécurité.
Wicri :
- topic : Décision.

English descriptors

KwdEn :
- Complexity, Computer theory, Cryptographic protocol, Decision, Deduction, Oracle, Security protocol, Verification.

Abstract

We provide a method for deciding the insecurity of cryptographic protocols in the presence of the standard Dolev-Yao intruder (with a finite number of sessions) extended with so-called oracle rules, i.e., deduction rules that satisfy certain conditions. As an instance of this general framework, we obtain that protocol insecurity is in NP for an intruder that can exploit the properties of the exclusive or (XOR) operator. This operator is frequently used in cryptographic protocols but cannot be handled in most protocol models. An immediate consequence of our proof is that checking whether a message can be derived by an intruder (using XOR) is in PTIME. We also apply our framework to an intruder that exploits properties of certain encryption modes such as cipher block chaining (CBC).

Url:

https://hal.inria.fr/inria-00103807

Affiliations:

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">An NP decision procedure for protocol insecurity with XOR</title>
<author><name sortKey="Chevalier, Yannick" sort="Chevalier, Yannick" uniqKey="Chevalier Y" first="Yannick" last="Chevalier">Yannick Chevalier</name>
<affiliation wicri:level="4"><inist:fA14 i1="01"><s1>LORIA-INRIA-Université Henri Poincaré</s1>
<s2>54506 Vandoeuvre-les-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
<orgName type="university">Université Henri Poincaré</orgName>
</affiliation>
</author>
<author><name sortKey="Kusters, Ralf" sort="Kusters, Ralf" uniqKey="Kusters R" first="Ralf" last="Küsters">Ralf Küsters</name>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Christian-Albrechts-Universität zu Kiel, Inst. f. Informatik</s1>
<s2>24098 Kiel</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<placeName><region type="land" nuts="2">Schleswig-Holstein</region>
<settlement type="city">Kiel</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michaël" last="Rusinowitch">Michaël Rusinowitch</name>
<affiliation wicri:level="4"><inist:fA14 i1="01"><s1>LORIA-INRIA-Université Henri Poincaré</s1>
<s2>54506 Vandoeuvre-les-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
<orgName type="university">Université Henri Poincaré</orgName>
</affiliation>
</author>
<author><name sortKey="Turuani, Mathieu" sort="Turuani, Mathieu" uniqKey="Turuani M" first="Mathieu" last="Turuani">Mathieu Turuani</name>
<affiliation wicri:level="4"><inist:fA14 i1="01"><s1>LORIA-INRIA-Université Henri Poincaré</s1>
<s2>54506 Vandoeuvre-les-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
<orgName type="university">Université Henri Poincaré</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">05-0253621</idno>
<date when="2005">2005</date>
<idno type="stanalyst">PASCAL 05-0253621 INIST</idno>
<idno type="RBID">Pascal:05-0253621</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000570</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000468</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000525</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000525</idno>
<idno type="wicri:doubleKey">0304-3975:2005:Chevalier Y:an:np:decision</idno>
<idno type="wicri:Area/Main/Merge">006662</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00103807</idno>
<idno type="url">https://hal.inria.fr/inria-00103807</idno>
<idno type="wicri:Area/Hal/Corpus">000D22</idno>
<idno type="wicri:Area/Hal/Curation">000D22</idno>
<idno type="wicri:Area/Hal/Checkpoint">004991</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">004991</idno>
<idno type="wicri:doubleKey">0304-3975:2005:Chevalier Y:an:np:decision</idno>
<idno type="wicri:Area/Main/Merge">006883</idno>
<idno type="wicri:Area/Main/Curation">006380</idno>
<idno type="wicri:Area/Main/Exploration">006380</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">An NP decision procedure for protocol insecurity with XOR</title>
<author><name sortKey="Chevalier, Yannick" sort="Chevalier, Yannick" uniqKey="Chevalier Y" first="Yannick" last="Chevalier">Yannick Chevalier</name>
<affiliation wicri:level="4"><inist:fA14 i1="01"><s1>LORIA-INRIA-Université Henri Poincaré</s1>
<s2>54506 Vandoeuvre-les-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
<orgName type="university">Université Henri Poincaré</orgName>
</affiliation>
</author>
<author><name sortKey="Kusters, Ralf" sort="Kusters, Ralf" uniqKey="Kusters R" first="Ralf" last="Küsters">Ralf Küsters</name>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Christian-Albrechts-Universität zu Kiel, Inst. f. Informatik</s1>
<s2>24098 Kiel</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<placeName><region type="land" nuts="2">Schleswig-Holstein</region>
<settlement type="city">Kiel</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michaël" last="Rusinowitch">Michaël Rusinowitch</name>
<affiliation wicri:level="4"><inist:fA14 i1="01"><s1>LORIA-INRIA-Université Henri Poincaré</s1>
<s2>54506 Vandoeuvre-les-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
<orgName type="university">Université Henri Poincaré</orgName>
</affiliation>
</author>
<author><name sortKey="Turuani, Mathieu" sort="Turuani, Mathieu" uniqKey="Turuani M" first="Mathieu" last="Turuani">Mathieu Turuani</name>
<affiliation wicri:level="4"><inist:fA14 i1="01"><s1>LORIA-INRIA-Université Henri Poincaré</s1>
<s2>54506 Vandoeuvre-les-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
<orgName type="university">Université Henri Poincaré</orgName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
<imprint><date when="2005">2005</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Complexity</term>
<term>Computer theory</term>
<term>Cryptographic protocol</term>
<term>Decision</term>
<term>Deduction</term>
<term>Oracle</term>
<term>Security protocol</term>
<term>Verification</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Décision</term>
<term>Oracle</term>
<term>Déduction</term>
<term>Vérification</term>
<term>Complexité</term>
<term>Informatique théorique</term>
<term>Protocole cryptographique</term>
<term>Protocole sécurité</term>
</keywords>
<keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Décision</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We provide a method for deciding the insecurity of cryptographic protocols in the presence of the standard Dolev-Yao intruder (with a finite number of sessions) extended with so-called oracle rules, i.e., deduction rules that satisfy certain conditions. As an instance of this general framework, we obtain that protocol insecurity is in NP for an intruder that can exploit the properties of the exclusive or (XOR) operator. This operator is frequently used in cryptographic protocols but cannot be handled in most protocol models. An immediate consequence of our proof is that checking whether a message can be derived by an intruder (using XOR) is in PTIME. We also apply our framework to an intruder that exploits properties of certain encryption modes such as cipher block chaining (CBC).</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
<li>France</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Schleswig-Holstein</li>
</region>
<settlement><li>Kiel</li>
<li>Vandœuvre-lès-Nancy</li>
</settlement>
<orgName><li>Université Henri Poincaré</li>
</orgName>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Chevalier, Yannick" sort="Chevalier, Yannick" uniqKey="Chevalier Y" first="Yannick" last="Chevalier">Yannick Chevalier</name>
</region>
<name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michaël" last="Rusinowitch">Michaël Rusinowitch</name>
<name sortKey="Turuani, Mathieu" sort="Turuani, Mathieu" uniqKey="Turuani M" first="Mathieu" last="Turuani">Mathieu Turuani</name>
</country>
<country name="Allemagne"><region name="Schleswig-Holstein"><name sortKey="Kusters, Ralf" sort="Kusters, Ralf" uniqKey="Kusters R" first="Ralf" last="Küsters">Ralf Küsters</name>
</region>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006380 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006380 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:05-0253621
   |texte=   An NP decision procedure for protocol insecurity with XOR
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

An NP decision procedure for protocol insecurity with XOR

An NP decision procedure for protocol insecurity with XOR

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.